#include <bits/stdc++.h>

using namespace std;

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 二叉树打家劫舍问题
// 测试链接 : https://leetcode.cn/problems/house-robber-iii/

class Solution 
{
private:
    // 全局变量，完成了X子树的遍历，返回之后
	// yes变成，X子树在偷头节点的情况下，最大的收益
    int yes;
    // 全局变量，完成了X子树的遍历，返回之后
	// no变成，X子树在不偷头节点的情况下，最大的收益
    int no;

    void f(TreeNode* root)
    {
        if(root == nullptr)
        {
            yes = no = 0;
            return;
        }

        int y = root->val;
        int n = 0;
        
        f(root->left);
        y += no;
        n += max(yes, no);
        f(root->right);
        y += no;
        n += max(yes, no);
        
        yes = y;
        no = n;
    }
    
public:
    int rob(TreeNode* root) 
    {
        f(root);
        return max(yes, no);
    }
};


class Solution 
{
private:
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* root)
    {
        if(root == nullptr)
            return {0, 0};
        
        vector<int>&& left = robTree(root->left);
        vector<int>&& right = robTree(root->right);
        // 偷当前节点
        int val1 = root->val + left[0] + right[0];
        // 不偷当前节点
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);

        return {val2, val1};
    }
public:
    int rob(TreeNode* root) 
    {
        vector<int>&& ret = robTree(root);
        return max(ret[0], ret[1]);
    }
};